/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/largest-palindrome-product
   @Language: C++
   @Datetime: 19-05-17 16:03
   */

class Solution {
public:
	/**
	 * @param n: the number of digit
	 * @return: the largest palindrome mod 1337
	 */
	int largestPalindrome(int n) {
		// write your code here
		const int begin=pow(10,n-1), end=pow(10,n);
		for(int i=end; i-->begin;){
			string str=to_string(i);
			long p=stol(str+string(str.rbegin(),str.rend()));
			for(long j=end-1; j>=sqrtl(p) && j>=begin; --j)
				if(p%j==0 && p/j>=begin && p/j<end) return p%1337;
		}
		return 9;
	}
};
